---
title: "8、整数删除"
created: 2025-11-28
tags:
  - 算法
---

# 8、整数删除

## 题目 [整数删除](https://www.lanqiao.cn/paper/3818/problem/3515/)

![[image-1a05d589.png]]

## 思路分析

怎么感觉像是模拟……有点难以置信

![[image-9304919c.png]]

肯定有个优化的点 但是 暴力模拟一定可以拿一半的分

先写着吧 看看能不能找到优化的点

浪费时间的地方主要是在 找这个最小的数 以及删除后的重新排列下标

一个设想是 用优先队列（小根堆） 加 pair 把所有的{数和下标}都存下来

这样就可以很容易地索引到最小的那个数和它的下标

真进行删除操作比较麻烦 设想是 用一个st数组来标记状态是否已删除

![[image-decc7834.png]]

但是更新左右会比较麻烦 干脆把左右也记录下来

用类似于链表的思路 删除一个节点后 左的右等于当前右 右的左等于当前左

居然和正解差不多 但是我这因为是一步一步优化来的 有点冗余 效率较低 有两个数据过不了 但是也够用了

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

struct vi{

    int val,idx;

    int left, right;

    bool operator<(const vi& other)const{

        if (val == other.val)

            return idx > other.idx;

        return val > other.val;

    }

};

const int N=5e5+10;

int a[N];

bool st[N];

int L[N],R[N];

priority_queue<vi> minheap;

int main() {

    int n, k;

    cin >> n >> k;

    for(int i = 1; i <= n; i++) {

        cin >> a[i];

        L[i]=i-1,R[i]=i+1;

        minheap.push({a[i], i, i-1, i+1});

    }

    while(k--){

        auto del = minheap.top();

        minheap.pop();

        while(st[del.idx] || a[del.idx] != del.val) {

            del = minheap.top();

            minheap.pop();

        }

        st[del.idx] = true;

        if(del.left >= 1) {

            a[del.left]+=del.val;

            R[del.left]=R[del.idx];

            minheap.push({a[del.left],del.left,L[del.left],R[del.left]});

        }

        if(del.right <= n) {

            a[del.right]+=del.val;

            L[del.right]=L[del.idx];

            minheap.push({a[del.right],del.right,L[del.right],R[del.right]});

        }

    }

    for(int i = 1; i <= n; i++) {

        if(!st[i]) {

            cout<<a[i]<<" ";

        }

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[7、子串简写|7、子串简写]] 🏠 [[00-刷题理模型]] ➡️ [[9、景区导游|9、景区导游]]